// #include<iostream>

// // 定义链表结构
// struct ListNode {
//     int val;
//     ListNode *next;
//     ListNode(int x) : val(x), next(nullptr) {}
// };

// class Solution {
// public:
//     ListNode* removeElements(ListNode* head, int val) {
//         ListNode *dummyHead = new ListNode(0); //
//         dummyHead->next = head; // 
//         ListNode *current = dummyHead; // 
//         while(current->next != NULL){
//             if(current->next->val == val){
//                 ListNode *tmp = current->next; // 先把待删除节点的位置保存，然后进行删除，防止内存泄漏
//                 current->next = current->next->next;
//                 delete tmp;
//             }
//             else{
//                 current = current->next;
//             }
//         }
//         head = dummyHead->next;
//         delete dummyHead;
//         return head;
//     }
// };

#include <iostream>
using namespace std;

// 定义链表节点结构
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        ListNode *dummyHead = new ListNode(0); // 使用虚拟头节点简化操作
        dummyHead->next = head;
        ListNode *current = dummyHead;
        while (current->next != nullptr) {
            if (current->next->val == val) { // 检查并删除满足条件的节点
                ListNode *temp = current->next;
                current->next = current->next->next;
                delete temp; // 释放内存
            } else {
                current = current->next;
            }
        }
        head = dummyHead->next;
        delete dummyHead; // 释放虚拟头节点的内存
        return head;
    }
};

// 创建链表
ListNode* createLinkedList(int arr[], int n) {
    if (n == 0) return nullptr;
    ListNode *head = new ListNode(arr[0]);
    ListNode *current = head;
    for (int i = 1; i < n; ++i) {
        current->next = new ListNode(arr[i]);
        current = current->next;
    }
    return head;
}

// 打印链表
void printLinkedList(ListNode* head) {
    ListNode *current = head;
    while (current != nullptr) {
        cout << current->val << " -> ";
        current = current->next;
    }
    cout << "NULL" << endl;
}

// 释放链表内存
void deleteLinkedList(ListNode* head) {
    while (head != nullptr) {
        ListNode *temp = head;
        head = head->next;
        delete temp;
    }
}

int main() {
    int n, val;
    cout << "Enter the number of nodes in the linked list: ";
    cin >> n;
    int *arr = new int[n];
    cout << "Enter " << n << " elements: ";
    for (int i = 0; i < n; ++i) {
        cin >> arr[i];
    }
    cout << "Enter the value to remove: ";
    cin >> val;

    ListNode *head = createLinkedList(arr, n);
    Solution solution;
    head = solution.removeElements(head, val);
    printLinkedList(head);

    deleteLinkedList(head);
    delete[] arr;
    return 0;
}
